#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<string.h>
using namespace std;
class Solution {
public:
    int book[2][205] = {0};   //第一列供搜索使用，第二列供第一个循环遍历时使用
    map<int, vector<int> >connected;   //二维矩阵转换为map，存储边信息
    void bfs(int start){
        int index = start-1;
        queue<int>Q;
        Q.push(start);
        //临时标记  //永久标记
        book[0][start] = book[1][start] = 1;
        while(!Q.empty()) {
            int node = Q.front();
            Q.pop();
            for(int n : connected[node])
                if(book[0][n] != 1){
                    Q.push(n);
                    //临时标记  //永久标记
                    book[0][n] = book[1][n] = 1; 
                } //如果该节点标记过，则标记后加入队列
        }
        memset(book[0],0,sizeof(book[0]));  //情况临时标记
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        //先处理原二维矩阵
        for(int i=0;i<isConnected.size(); i++)
            for(int j=0;j<isConnected[i].size();j++){
                if(i==j)
                    continue;
                if(isConnected[i][j] == 1){
                    //说明相连,存在一条边
                    (connected[i+1]).push_back(j+1);
                }
            }
        int ans = 0;
        for(int i=1;i<=isConnected.size();i++){
            if(book[1][i] == 1)
                continue;   //说明该节点已被搜索过
            book[1][i]  = 1;
            bfs(i); //将节点i，广搜一次，并标记所有与之相连的节点
            ans++;
        }
        return ans;
    }
    /*      //如果可以，也可以更换成并查集写法
    int Find(vector<int>& parent, int index) {
        if (parent[index] != index) {
            parent[index] = Find(parent, parent[index]);
        }
        return parent[index];
    }

    void Union(vector<int>& parent, int index1, int index2) {
        parent[Find(parent, index1)] = Find(parent, index2);
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities = isConnected.size();
        vector<int> parent(cities);
        for (int i = 0; i < cities; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < cities; i++) {
            for (int j = i + 1; j < cities; j++) {
                if (isConnected[i][j] == 1) {
                    Union(parent, i, j);
                }
            }
        }
        int provinces = 0;
        for (int i = 0; i < cities; i++) {
            if (parent[i] == i) {
                provinces++;
            }
        }
        return provinces;
    }
    */
};
int main(){
    vector<vector<int>> isConnected = {{1,1,0},{1,1,0},{0,0,1}};
    Solution *s = new Solution();
    cout<<s->findCircleNum(isConnected)<<endl;
    return 0;
}